吴师兄学算法

# LeetCode 72、编辑距离

# 一、题目描述

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

  • 1、插入一个字符
  • 2、删除一个字符
  • 3、替换一个字符

# 二、题目解析

# 三、参考代码

# 1、Java 代码

class Solution {
    public int minDistance(String word1, String word2) {
        
        // 获取字符串 word1 的长度
        int L1 = word1.length();

        // 获取字符串 word2 的长度
        int L2 = word2.length();

        // 设置二维数组 dp 用来储存 word1 的前 i 个字符转换为 word2 的前 j 个字符最少操作数
        // dp[0][0] 表示 word1 的前 0 个字符转换为 word2 的前 0 个字符最少操作数
        // dp[0][j] 表示 word1 的前 0 个字符转换为 word2 的前 j 个字符最少操作数
        // dp[i][0] 表示 word1 的前 i 个字符转换为 word2 的前 0 个字符最少操作数
        // dp[i][j] 表示 word1 的前 i 个字符转换为 word2 的前 j 个字符最少操作数
        // dp[L1][L2] 表示 word1 的前 L1 个字符转换为 word2 的前 L2 个字符最少操作数
        int[][] dp = new int[L1 + 1][L2 + 1];

        // dp[i][0] 表示 word1 的前 i 个字符转换为 word2 的前 0 个字符最少操作数
        // dp[i][0] 相当于给二维数组 dp 的第一列进行赋值操作
        // 只需要每次执行删除操作，就可以把 word1 的字符删除到 0 个字符
        for(int i = 0 ; i <= L1 ; i++){
            // dp[1][0] 表示需要删除 1 次才能删除到 0 个字符
            // dp[2][0] 表示需要删除 2 次才能删除到 2 个字符
            // dp[i][0] 表示需要删除 i 次才能删除到 2 个字符
            dp[i][0] = i;
        }

        // dp[0][j] 表示 word1 的前 0 个字符转换为 word2 的前 j 个字符最少操作数
        // dp[0][j] 相当于给二维数组 dp 的第一行进行赋值操作
        // 只需要每次执行插入操作，就可以把 word1 的字符转行为 j 个字符
        for(int j = 0 ;j <= L2 ; j++){
            // dp[0][1] 表示需要插入 1 次才能得到 1 个字符
            // dp[0][2] 表示需要插入 2 次才能得到 2 个字符
            // dp[0][j] 表示需要插入 j 次才能得到 j 个字符
            dp[0][j] = j;
        }


        // 通过两个 for 循环，设置二维数组 dp 中的所有元素的值
        // i 从 word1 的第 1 个字符一直到 L1 个字符
        for(int i = 1 ; i <= L1 ; i++){

            // j 从 word2 的第 1 个字符一直到 L2 个字符
            for(int j = 1 ; j <= L2 ; j++){

                // 二维数组 dp 的下标是从 (0,0) 开始的
                // 所以 dp[i][j] 表示的是 word1 中前 i 个字符即位置为 i - 1 的字符
                // 转换为 word2 中前 j 个字符即位置为 j - 1 的字符所需要的最少操作数
                // 如果此时 word1 中第 i - 1 个位置的字符（即当前遍历 i 时的字符）
                // 与 word2 中第 j - 1 个位置的字符【相等】（即当前遍历 j 时的字符）
                // 说明 word1 的前 i - 1 个字符转换为 word2 中前 j - 1 个字符成功后，
                // word1 的前 i 个字符也就成功转换为 word2 的前 j 个字符了
                if(word1.charAt(i - 1) == word2.charAt(j - 1)){

                    // dp[i][j] 表示 word1 的前 i 个字符转换为 word2 的前 j 个字符最少操作数
                    // dp[i - 1][j - 1] 表示 word1 的前 i - 1 个字符转换为 word2 的前 j -1 个字符最少操作数
                    // 比如 word1 为 abcd，word2 为 efgd
                    // 此时 i = 4，j = 4
                    // 由于 word1.charAt(4 - 1) = d
                    // word2.charAt(4 - 1) = d
                    // 所以如果知道了 abc 转换为 efg 的最少操作数，那么结果也就出来了
                    // d --> d 不需要执行任何操作
                    dp[i][j] = dp[i - 1][j - 1];

                    // 否则，说明 word1 中第 i - 1 个位置的字符（即当前遍历 i 时的字符）
                    // 与 word2 中第 j - 1 个位置的字符【不相等】（即当前遍历 j 时的字符）
                }else{
                    
                    // 那么 dp[i][j]  可以从以下三种状态转换过来
                    // 1、word1(L1-1) ——> word2(L2-1)
                    // 2、word1(L1-1) ——> word2(L2)
                    // 3、word1(L1) ——> word2(L2-1)
                    // word1(L1-1) ——> word2(L2-1) 的最少操作数是 dp[i - 1][j - 1]
                    // word1(L1-1) ——> word2(L2) 的最少操作数是 dp[i - 1][j]
                    // word1(L1) ——> word2(L2-1) 的最少操作数是 dp[i][j - 1])
                    // 选这三种状态的较小值后，
                    // 1、如果是 word1(L1-1) ——> word2(L2-1) 过来的，再执行 1 次替换操作
                    // 2、如果是 word1(L1-1) ——> word2(L2)   过来的，再执行 1 次删除操作
                    // 3、如果是 word1(L1) ——> word2(L2-1)   过来的，再执行 1 次插入操作
                    dp[i][j] = Math.min(dp[i - 1][j - 1],Math.min(dp[i - 1][j],dp[i][j - 1])) + 1;
                }
            }
        }
        // dp[L1][L2] 表示 word1 的前 L1 个字符转换为 word2 的前 L2 个字符最少操作数
        // 把这个结果进行返回
        return dp[L1][L2];

    }
}

# **2、**C++ 代码

class Solution {
public:
    int minDistance(string word1, string word2) {

        // 获取字符串 word1 的长度
        int L1 = word1.length();

        // 获取字符串 word2 的长度
        int L2 = word2.length();

        // 设置二维数组 dp 用来储存 word1 的前 i 个字符转换为 word2 的前 j 个字符最少操作数
        // dp[0][0] 表示 word1 的前 0 个字符转换为 word2 的前 0 个字符最少操作数
        // dp[0][j] 表示 word1 的前 0 个字符转换为 word2 的前 j 个字符最少操作数
        // dp[i][0] 表示 word1 的前 i 个字符转换为 word2 的前 0 个字符最少操作数
        // dp[i][j] 表示 word1 的前 i 个字符转换为 word2 的前 j 个字符最少操作数
        // dp[L1][L2] 表示 word1 的前 L1 个字符转换为 word2 的前 L2 个字符最少操作数
        auto dp = vector< vector <int> > ( L1 + 1,vector <int> ( L2 + 1 ));

        // dp[i][0] 表示 word1 的前 i 个字符转换为 word2 的前 0 个字符最少操作数
        // dp[i][0] 相当于给二维数组 dp 的第一列进行赋值操作
        // 只需要每次执行删除操作，就可以把 word1 的字符删除到 0 个字符
        for(int i = 0 ; i <= L1 ; i++){
            // dp[1][0] 表示需要删除 1 次才能删除到 0 个字符
            // dp[2][0] 表示需要删除 2 次才能删除到 2 个字符
            // dp[i][0] 表示需要删除 i 次才能删除到 2 个字符
            dp[i][0] = i;
        }

        // dp[0][j] 表示 word1 的前 0 个字符转换为 word2 的前 j 个字符最少操作数
        // dp[0][j] 相当于给二维数组 dp 的第一行进行赋值操作
        // 只需要每次执行插入操作，就可以把 word1 的字符转行为 j 个字符
        for(int j = 0 ;j <= L2 ; j++){
            // dp[0][1] 表示需要插入 1 次才能得到 1 个字符
            // dp[0][2] 表示需要插入 2 次才能得到 2 个字符
            // dp[0][j] 表示需要插入 j 次才能得到 j 个字符
            dp[0][j] = j;
        }


        // 通过两个 for 循环，设置二维数组 dp 中的所有元素的值
        // i 从 word1 的第 1 个字符一直到 L1 个字符
        for(int i = 1 ; i <= L1 ; i++){

            // j 从 word2 的第 1 个字符一直到 L2 个字符
            for(int j = 1 ; j <= L2 ; j++){

                // 二维数组 dp 的下标是从 (0,0) 开始的
                // 所以 dp[i][j] 表示的是 word1 中前 i 个字符即位置为 i - 1 的字符
                // 转换为 word2 中前 j 个字符即位置为 j - 1 的字符所需要的最少操作数
                // 如果此时 word1 中第 i - 1 个位置的字符（即当前遍历 i 时的字符）
                // 与 word2 中第 j - 1 个位置的字符【相等】（即当前遍历 j 时的字符）
                // 说明 word1 的前 i - 1 个字符转换为 word2 中前 j - 1 个字符成功后，
                // word1 的前 i 个字符也就成功转换为 word2 的前 j 个字符了
                if(word1[i - 1] == word2[j - 1]){
                    // dp[i][j] 表示 word1 的前 i 个字符转换为 word2 的前 j 个字符最少操作数
                    // dp[i - 1][j - 1] 表示 word1 的前 i - 1 个字符转换为 word2 的前 j -1 个字符最少操作数
                    // 比如 word1 为 abcd，word2 为 efgd
                    // 此时 i = 4，j = 4
                    // 由于 word1.charAt(4 - 1) = d
                    // word2.charAt(4 - 1) = d
                    // 所以如果知道了 abc 转换为 efg 的最少操作数，那么结果也就出来了
                    // d --> d 不需要执行任何操作
                    dp[i][j] = dp[i - 1][j - 1];

                    // 否则，说明 word1 中第 i - 1 个位置的字符（即当前遍历 i 时的字符）
                    // 与 word2 中第 j - 1 个位置的字符【不相等】（即当前遍历 j 时的字符）
                }else{
                    
                    // 那么 dp[i][j]  可以从以下三种状态转换过来
                    // 1、word1(L1-1) ——> word2(L2-1)
                    // 2、word1(L1-1) ——> word2(L2)
                    // 3、word1(L1) ——> word2(L2-1)
                    // word1(L1-1) ——> word2(L2-1) 的最少操作数是 dp[i - 1][j - 1]
                    // word1(L1-1) ——> word2(L2) 的最少操作数是 dp[i - 1][j]
                    // word1(L1) ——> word2(L2-1) 的最少操作数是 dp[i][j - 1])
                    // 选这三种状态的较小值后，
                    // 1、如果是 word1(L1-1) ——> word2(L2-1) 过来的，再执行 1 次替换操作
                    // 2、如果是 word1(L1-1) ——> word2(L2)   过来的，再执行 1 次删除操作
                    // 3、如果是 word1(L1) ——> word2(L2-1)   过来的，再执行 1 次插入操作
                    dp[i][j] = min(dp[i - 1][j - 1],min(dp[i - 1][j],dp[i][j - 1])) + 1;
                }
            }
        }
        // dp[L1][L2] 表示 word1 的前 L1 个字符转换为 word2 的前 L2 个字符最少操作数
        // 把这个结果进行返回
        return dp[L1][L2];
    }
};

# 3、Python 代码

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        # 获取字符串 word1 的长度
        L1 = len(word1)

        # 获取字符串 word2 的长度
        L2 = len(word2)

        # 设置二维数组 dp 用来储存 word1 的前 i 个字符转换为 word2 的前 j 个字符最少操作数
        # dp[0][0] 表示 word1 的前 0 个字符转换为 word2 的前 0 个字符最少操作数
        # dp[0][j] 表示 word1 的前 0 个字符转换为 word2 的前 j 个字符最少操作数
        # dp[i][0] 表示 word1 的前 i 个字符转换为 word2 的前 0 个字符最少操作数
        # dp[i][j] 表示 word1 的前 i 个字符转换为 word2 的前 j 个字符最少操作数
        # dp[L1][L2] 表示 word1 的前 L1 个字符转换为 word2 的前 L2 个字符最少操作数
        dp = [[0] * (L2 + 1) for _ in range( L1 + 1)]

        # dp[i][0] 表示 word1 的前 i 个字符转换为 word2 的前 0 个字符最少操作数
        # dp[i][0] 相当于给二维数组 dp 的第一列进行赋值操作
        # 只需要每次执行删除操作，就可以把 word1 的字符删除到 0 个字符
        for i in range(L1 + 1):
            # dp[1][0] 表示需要删除 1 次才能删除到 0 个字符
            # dp[2][0] 表示需要删除 2 次才能删除到 2 个字符
            # dp[i][0] 表示需要删除 i 次才能删除到 2 个字符
            dp[i][0] = i
        

        # dp[0][j] 表示 word1 的前 0 个字符转换为 word2 的前 j 个字符最少操作数
        # dp[0][j] 相当于给二维数组 dp 的第一行进行赋值操作
        # 只需要每次执行插入操作，就可以把 word1 的字符转行为 j 个字符
        for j in range( L2 + 1):
            # dp[0][1] 表示需要插入 1 次才能得到 1 个字符
            # dp[0][2] 表示需要插入 2 次才能得到 2 个字符
            # dp[0][j] 表示需要插入 j 次才能得到 j 个字符
            dp[0][j] = j
        


        # 通过两个 for 循环，设置二维数组 dp 中的所有元素的值
        # i 从 word1 的第 1 个字符一直到 L1 个字符
        for i in range( 1 , L1 + 1):

            # j 从 word2 的第 1 个字符一直到 L2 个字符
            for j in range( 1 , L2 + 1):

                # 二维数组 dp 的下标是从 (0,0) 开始的
                # 所以 dp[i][j] 表示的是 word1 中前 i 个字符即位置为 i - 1 的字符
                # 转换为 word2 中前 j 个字符即位置为 j - 1 的字符所需要的最少操作数
                # 如果此时 word1 中第 i - 1 个位置的字符（即当前遍历 i 时的字符）
                # 与 word2 中第 j - 1 个位置的字符【相等】（即当前遍历 j 时的字符）
                # 说明 word1 的前 i - 1 个字符转换为 word2 中前 j - 1 个字符成功后，
                # word1 的前 i 个字符也就成功转换为 word2 的前 j 个字符了
                if word1[i - 1] == word2[j - 1] : 

                    # dp[i][j] 表示 word1 的前 i 个字符转换为 word2 的前 j 个字符最少操作数
                    # dp[i - 1][j - 1] 表示 word1 的前 i - 1 个字符转换为 word2 的前 j -1 个字符最少操作数
                    # 比如 word1 为 abcd，word2 为 efgd
                    # 此时 i = 4，j = 4
                    # 由于 word1.charAt(4 - 1) = d
                    # word2.charAt(4 - 1) = d
                    # 所以如果知道了 abc 转换为 efg 的最少操作数，那么结果也就出来了
                    # d --> d 不需要执行任何操作
                    dp[i][j] = dp[i - 1][j - 1]

                    # 否则，说明 word1 中第 i - 1 个位置的字符（即当前遍历 i 时的字符）
                    # 与 word2 中第 j - 1 个位置的字符【不相等】（即当前遍历 j 时的字符）
                else:
                    
                    # 那么 dp[i][j]  可以从以下三种状态转换过来
                    # 1、word1(L1-1) ——> word2(L2-1)
                    # 2、word1(L1-1) ——> word2(L2)
                    # 3、word1(L1) ——> word2(L2-1)
                    # word1(L1-1) ——> word2(L2-1) 的最少操作数是 dp[i - 1][j - 1]
                    # word1(L1-1) ——> word2(L2) 的最少操作数是 dp[i - 1][j]
                    # word1(L1) ——> word2(L2-1) 的最少操作数是 dp[i][j - 1])
                    # 选这三种状态的较小值后，
                    # 1、如果是 word1(L1-1) ——> word2(L2-1) 过来的，再执行 1 次替换操作
                    # 2、如果是 word1(L1-1) ——> word2(L2)   过来的，再执行 1 次删除操作
                    # 3、如果是 word1(L1) ——> word2(L2-1)   过来的，再执行 1 次插入操作
                    dp[i][j] = min(dp[i - 1][j - 1],min(dp[i - 1][j],dp[i][j - 1])) + 1
    
        # dp[L1][L2] 表示 word1 的前 L1 个字符转换为 word2 的前 L2 个字符最少操作数
        # 把这个结果进行返回
        return dp[L1][L2]

← LeetCode 139、单词拆分 →